package com.Oct_TwentySix;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 862. 和至少为 K 的最短子数组
 * 给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
 *
 * 子数组 是数组中 连续 的一部分。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/26 15:02
 */

public class Solution862 {

    public int shortestSubarray(int[] nums, int k) {
        long[] ans= new long[nums.length + 1];
        int maxLen=ans.length;
        for (int i = 0; i < nums.length; i++) {
            ans[i+1]=ans[i]+nums[i];
        }
        Deque<Integer> deque=new LinkedList<>();
        for (int i = 0; i < nums.length+1; i++) {
            while (!deque.isEmpty()&&ans[i]<=ans[deque.getLast()])
            {
                deque.pollLast();
            }
            while (!deque.isEmpty()&&(ans[i]-ans[deque.getFirst()])>=k)
            {
                int minLen=i-deque.pollFirst();
                if (minLen<maxLen)
                {
                    maxLen=minLen;
                }
            }
            deque.addLast(i);
        }
        return maxLen==ans.length?-1:maxLen;
    }

    public static void main(String[] args) {
        Solution862 solution862=new Solution862();
        System.out.println(solution862.shortestSubarray(new int[]{2,-1,2},3));
    }

}
